Search for: All records

Given a function f from the set [N] to a d-dimensional integer grid, we consider data structures that allow efficient orthogonal range searching queries in the image of f, without explicitly storing it. We show that, if f is of the form [N] → [2w]d for some w = polylog(N) and is computable in constant time, then, for any 0 < α < 1, we can obtain a data structure using Õ(N1-α/3) words of space such that, for a given d-dimensional axis-aligned box B, we can search for some x ∈ [N] such that f (x) ∈ B in time Õ(Nα). This result is obtained simply by combining integer range searching with the Fiat-Naor function inversion scheme, which was already used in data-structure problems previously. We further obtain • data structures for range counting and reporting, predecessor, selection, ranking queries, and combinations thereof, on the set f ([N]), • data structures for preimage size and preimage selection queries for a given value of f, and • data structures for selection and ranking queries on geometric quantities computed from tuples of points in d-space. These results unify and generalize previously known results on 3SUM-indexing and string searching, and are widely applicable as a black box to a variety of problems. In particular, we give a data structure for a generalized version of gapped string indexing, and show how to preprocess a set of points on an integer grid in order to efficiently compute (in sublinear time), for points contained in a given axis-aligned box, their Theil-Sen estimator, the kth largest area triangle, or the induced hyperplane that is the kth furthest from the origin. 

We present subquadratic algorithms in the algebraic decision-tree model for several 3Sum-hard geometric problems, all of which can be reduced to the following question: Given two sets A, B, each consisting of n pairwise disjoint segments in the plane, and a set C of n triangles in the plane, we want to count, for each triangle Δ ∈ C, the number of intersection points between the segments of A and those of B that lie in Δ. The problems considered in this paper have been studied by Chan (2020), who gave algorithms that solve them, in the standard real-RAM model, in O((n²/log²n) log^O(1) log n) time. We present solutions in the algebraic decision-tree model whose cost is O(n^{60/31+ε}), for any ε > 0. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal, Aronov, Ezra, and Zahl (2020). A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the order type of the lines, a "handicap" that turns out to be beneficial for speeding up our algorithm. 

We prove that some exact geometric pattern matching problems reduce in linear time to 𝑘-SUM when the pattern has a fixed size 𝑘. This holds in the real RAM model for searching for a similar copy of a set of 𝑘≥3 points within a set of n points in the plane, and for searching for an affine image of a set of 𝑘≥𝑑+2 points within a set of n points in d-space. As corollaries, we obtain improved real RAM algorithms and decision trees for the two problems. In particular, they can be solved by algebraic decision trees of near-linear height.